// 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

// 说明: 叶子节点是指没有子节点的节点。

// 示例:
// 给定如下二叉树，以及目标和 sum = 22，

//               5
//              / \
//             4   8
//            /   / \
//           11  13  4
//          /  \    / \
//         7    2  5   1
// 返回:

// [
//    [5,4,11,2],
//    [5,8,4,5]
// ]

#include "stdc++.h"

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 回溯，深搜
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res{};
        vector<int> vec{};
        if (root) DFS(res, vec, root, sum);
        return res;
    }
    void DFS(vector<vector<int>>& res, vector<int>& vec, TreeNode* root, int sum) {
        vec.push_back(root->val);
        if (root->val == sum && !root->left && !root->right)
            res.push_back(vec);
        if (root->left) DFS(res, vec, root->left, sum - root->val);
        if (root->right) DFS(res, vec, root->right, sum - root->val);
        vec.pop_back();
    }
};

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res{};
        vector<int> path{};
        if (root != nullptr) DFS(root, sum, path, res);
        return res;
    }
    void DFS(TreeNode* node, int sum, vector<int>& path, vector<vector<int>>& res) {
        path.push_back(node->val);
        if (node->left == nullptr && node->right == nullptr && node->val == sum) {
            res.push_back(path);
        }
        if (node->left != nullptr) {
            DFS(node->left, sum - node->val, path, res);
        }
        if (node->right != nullptr) {
            DFS(node->right, sum - node->val, path, res);
        }
        path.pop_back();
    }
};

/* dfs
时间复杂度：O(n^2)
空间复杂度：O(n)
*/
class Solution {
public:
    vector<vector<int>> paths{};
    vector<int> path{};
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (root != nullptr) {
            dfs(root, sum);
        }
        return paths;
    }
    void dfs(TreeNode* root, int sum) {
        path.push_back(root->val);
        if (root->left == nullptr && root->right == nullptr && root->val == sum) {
            paths.push_back(path);
        }
        if (root->left != nullptr) {
            dfs(root->left, sum - root->val);
        }
        if (root->right != nullptr) {
            dfs(root->right, sum - root->val);
        }
        path.pop_back();
    }
};

/* bfs
时间复杂度：O(n^2)
空间复杂度：O(n)
*/
class Solution {
private:
    vector<vector<int>> paths{};
    unordered_map<TreeNode*, TreeNode*> parent{};
public:
    void getPath(TreeNode* node) {
        vector<int> temp{};
        while (node != nullptr) {
            temp.emplace_back(node->val);
            node = parent[node];
        }
        reverse(temp.begin(), temp.end());
        paths.emplace_back(temp);
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if (root == nullptr) {
            return {};
        }
        queue<TreeNode*> node_queue{};
        node_queue.emplace(root);
        queue<int> sum_queue{};
        sum_queue.emplace(0);
        while (!node_queue.empty()) {
            TreeNode* node = node_queue.front();
            node_queue.pop();
            int rec = sum_queue.front() + node->val;
            sum_queue.pop();
            if (node->left == nullptr && node->right == nullptr) {
                if (rec == sum) {
                    getPath(node);
                }
            } else {
                if (node->left != nullptr) {
                    parent[node->left] = node;
                    node_queue.emplace(node->left);
                    sum_queue.emplace(rec);
                }
                if (node->right != nullptr) {
                    parent[node->right] = node;
                    node_queue.emplace(node->right);
                    sum_queue.emplace(rec);
                }
            }
        }
        return paths;
    }
};